#include <Windows.h>

#define N 12
#define STRLEN(x) (sizeof(x)/sizeof(TCHAR) - 1)

class CUI
{
private:
    HANDLE Output, Input;
public:
    CUI(short width = 128, short height = 64, char * ConsoleName = "Console Window")
    {
        char            buffer[255];
        COORD           cCoord;
        SMALL_RECT      sRect;
            
        AllocConsole();
        Output = GetStdHandle(STD_OUTPUT_HANDLE);
        Input = GetStdHandle(STD_INPUT_HANDLE);
        CharToOem(ConsoleName, (char*)&buffer);
        SetConsoleTitle(buffer);
        cCoord.X = width;
        cCoord.Y = height;
        SetConsoleScreenBufferSize(Output,cCoord);
        sRect.Left = 0;
        sRect.Right = width-1;
        sRect.Top = 0;
        sRect.Bottom = height-1;
        SetConsoleWindowInfo(Output, true, &sRect);
    }
    ~CUI(void)
    {
        FreeConsole();
    }
    CUI& Out(char * _text)
    {
        unsigned long   num;
        char            buffer[255];
 
        CharToOem(_text, (char*)&buffer);
        WriteConsole(Output, buffer, lstrlen(buffer), &num, NULL);
        return *this;
    }
    CUI& Out(int _text)
    {
        unsigned long   num;
        char            buffer[255];
 
        wsprintf(buffer, "%i", _text);
        WriteConsole(Output, buffer, lstrlen(buffer), &num, NULL);
        return *this;
    }
    CUI& NewLine(void)
    {
        unsigned long   num;
 
        WriteConsole(Output, "\n\r", 2, &num, NULL);
        return *this;
    }
};

void swap(int *x, int i, int j)
{
    int c = x[i];
    x[i] = x[j];
    x[j] = c;
}

int main()
{ 
	CUI Console1(80,25,"Console");
	Console1.Out("Start").NewLine();
    int c[N];
    int o[N];
    int a[N];
    int j;
    int s;
    int q;

    int iterationCount = 0;
    int iterCount = 0;

    int start = N;
    int minway[15];
    int MIN = -1;
    int waypoints[15];
    int wayPrice = 0;
    int A = 0;
    int B = 0;
    for (int i = 0; i < N+2; i++)
    {
        waypoints[i] = -1;
        minway[i] = -1;
    }
    waypoints[0] = start;
    waypoints[N+1] = start;

    minway[0] = start;
    minway[N+1] = start;

    int prices[14][14] =
    {
        0,      1,      2,      3,      4,      -1,     -1,		6,		1,      1,      2,      3,      4,		1,
        1,      0,      1,      4,      -1,     6,      1,      6,      6,      1,      2,      3,      4,		1,
        2,      1,      0,      4,      5,      6,      7,      8,      8,      1,      2,      3,      4,		1,
        3,      4,      4,      0,      5,      6,      7,      8,      8,      1,      2,      3,      4,		1,
        4,      -1,     5,      5,      0,      -1,     1,      6,      3,      1,      2,      3,      4,		1,
        -1,		6,		6,      6,      -1,     0,      7,      8,      8,      1,      2,      3,      4,		1,
        -1,		1,		7,      7,      1,      7,      0,      8,      8,      1,      2,      3,      4,		1,
        6,      6,      8,      8,      6,      8,      8,      0,      -1,     1,      2,      3,      4,		1,
        1,      6,      8,      8,      3,      8,      8,      -1,     0,      1,      2,      3,      4,		1,
        1,      1,      1,      1,      1,      1,      1,      1,      1,      0,      1,      1,      1,		1,
        2,      2,      2,      2,      2,      2,      2,      2,      2,      2,      0,      2,      2,		1,
        3,      3,      3,      3,      3,      3,      3,      3,      3,      3,      3,      0,      3,		1,
        4,      4,      4,      4,      4,      4,      4,      4,      4,      4,      4,      4,      0,		1,
        1,      1,      1,      1,      1,      1,      1,      1,      1,      1,		1,		1,		1,		0
    };

    //P1
    for (int i = 0; i < N; i++)
    {
        c[i]=0;
        o[i]=1;
        a[i]=i;
    }

    //P2
P2: {
        iterationCount++;
        if (iterationCount % 1000000 == 0)
        {
			Console1.Out(iterationCount / 1000000).NewLine();
        }

        for (int i = 1; i < N+1; i++)
        {
            waypoints[i] = a[i-1];
        }

        wayPrice = 0;
        for (int i = 0; i < N+1; i++)
        {
            A = waypoints[i];
            B = waypoints[i+1];
            wayPrice += prices[A][B];
            if (prices[A][B] == -1)
                goto P3;
        }
        wayPrice += prices[A][0];

        if (wayPrice < MIN || MIN == -1)
        {
            MIN = wayPrice;
            for (int i = 1; i < N+1; i++)
            {
                minway[i] = a[i-1];
            }
        }
    }

    //P3
P3:     j = N;
    s = 0;

    //P4
P4: q = c[j-1] + o[j-1];
    if (q < 0)
        goto P7;
    if (q == j)
        goto P6;

    //P5
//P5: 
	swap(a, j-c[j-1]+s-1, j-q+s-1);
    c[j-1] = q;
    goto P2;

    //P6
P6: if (j == 1)
        goto END;
    else
        s++;

    //P7
P7:     o[j-1] = o[j-1] * -1;
    j--;
    goto P4;



END:

    //int test1 = minway[0];
    //int test2 = MIN;
    //int test3 = iterationCount;

	Console1.Out("\nMinWay: ");
    for (int i = 0; i < N+2; i++)
	{
        Console1.Out(minway[i]);
		Console1.Out(" ");
	}
    Console1.Out("\nPrice: ");
	Console1.Out(MIN);
    return 0;
}